323. Number of Connected Components in an Undirected Graph
Medium

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

 

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

 

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.
Accepted
158,637
Submissions
270,406
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.68 (19 votes)

Premium

Solution


Approach 1: Depth-First Search (DFS)

Intuition

If you're not familiar with DFS, check out our Explore Card.

In an undirected graph, a connected component is a subgraph in which each pair of vertices is connected via a path. So essentially, all vertices in a connected component are reachable from one another.

Let's see how we can use DFS to solve the problem. If we run DFS, starting from a particular vertex, it will continue to visit the vertices depth-wise until there are no more adjacent vertices left to visit. Thus, it will visit all of the vertices within the connected component that contains the starting vertex. Each time we finish exploring a connected component, we can find another vertex that has not been visited yet, and start a new DFS from there. The number of times we start a new DFS will be the number of connected components.

Here is an example illustrating this approach.

fig

Figure 1. An example demonstrating the DFS approach.

Algorithm

  1. Create an adjacency list such that adj[v] contains all the adjacent vertices of vertex v.
  2. Initialize a hashmap or array, visited, to track the visited vertices.
  3. Define a counter variable and initialize it to zero.
  4. Iterate over each vertex in edges, and if the vertex is not already in visited, start a DFS from it. Add every vertex visited during the DFS to visited.
  5. Every time a new DFS starts, increment the counter variable by one.
  6. At the end, the counter variable will contain the number of connected components in the undirected graph.

Complexity Analysis

Here EE = Number of edges, VV = Number of vertices.

  • Time complexity: O(E+V){O}(E + V).

    Building the adjacency list will take O(E){O}(E) operations, as we iterate over the list of edges once, and insert each edge into two lists.

    During the DFS traversal, each vertex will only be visited once. This is because we mark each vertex as visited as soon as we see it, and then we only visit vertices that are not marked as visited. In addition, when we iterate over the edge list of each vertex, we look at each edge once. This has a total cost of O(E+V){O}(E + V).

  • Space complexity: O(E+V){O}(E + V).

    Building the adjacency list will take O(E){O}(E) space. To keep track of visited vertices, an array of size O(V){O}(V) is required. Also, the run-time stack for DFS will use O(V){O}(V) space.


Approach 2: Disjoint Set Union (DSU)

Imagine we have a graph with N vertices and 0 edges. The number of connected components will be N in that graph.

fig

Let's now add the edge from vertex 1 to vertex 2. This will decrease the number of components by 1. This is because vertices 1 and 2 are now in the same component.

fig

When we then add the edge from vertex 2 to vertex 3, the number of components will decrease by 1 again.

fig

However, this pattern will not continue when we add the edge from vertex 1 to vertex 3. The number of components will not change because vertices 1, 2, and 3 are already in the same component.

fig

The above observation is the main intuition behind the DSU approach.

Algorithm

  1. Initialize a variable count with the number of vertices in the input.
  2. Traverse all of the edges one by one, performing the union-find method combine on each edge. If the endpoints are already in the same set, then keep traversing. If they are not, then decrement count by 1.
  3. After traversing all of the edges, the variable count will contain the number of components in the graph.

Complexity Analysis

Here EE = Number of edges, VV = Number of vertices.

  • Time complexity: O(Eα(n))O(E\cdotα(n)).

    Iterating over every edge requires O(E)O(E) operations, and for every operation, we are performing the combine method which is O(α(n))O(α(n)), where α(n) is the inverse Ackermann function.

  • Space complexity: O(V)O(V).

    Storing the representative/immediate-parent of each vertex takes O(V)O(V) space. Furthermore, storing the size of components also takes O(V)O(V) space.



Report Article Issue

Comments: 8
hansrajdas's avatar
Read More

Pyton union find solution

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xset = self.find(x)
        yset = self.find(y)
        if xset == yset:
            return
        if self.rank[xset] > self.rank[yset]:
            self.parent[yset] = self.parent[xset]
        elif self.rank[xset] < self.rank[yset]:
            self.parent[xset] = self.parent[yset]
        else:
            self.parent[xset] = self.parent[yset]
            self.rank[yset] += 1
            
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        ds = DSU(n)
        for edge in edges:
            ds.union(edge[0], edge[1])
        
        parent = set()
        for i in range(n):
            parent.add(ds.find(i))
        return len(parent)

9
Reply
Share
Report
shreshtavinayak's avatar
Read More

Python DFS Solution:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        count = 0
        graph = [[] for _ in range(n)]
        seen = [False for _ in range(n)]
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
            
        def dfs(node):
            for adj in graph[node]:
                if not seen[adj]:
                    seen[adj] = True
                    dfs(adj)
                    
        for i in range(n):
            if not seen[i]:
                count += 1
                seen[i] = True
                dfs(i)
                
        return count

6
Reply
Share
Report
buvaneshwarant's avatar
Read More

shouldn't the answer to this input be 1? [[2,3],[1,2],[1,3]]
because all the nodes are connected. Don't understand why it would be 2.
very confusing.
based of their sample inputs and outputs in the description, the output for the input in question should be 1.
this is my python solution.
class Solution(object):

def countComponents(self, n, edges):

    from collections import defaultdict
    adjacency_list = defaultdict(list)

    for cNode, nNode in edges:
        adjacency_list[cNode].append(nNode)
        adjacency_list[nNode].append(cNode)

    seen = {}
          
    i = 0

    keys = list(adjacency_list.keys())

    while keys:  
        i += 1
        stack = [keys[0]]
        
        while stack:
            parent = stack.pop()              

            for child in adjacency_list[parent]:                    
                if child in seen:
                    continue 
                seen[child] = True
                stack.append(child) 
                keys.remove(child)

    return i

2
Show 8 replies
Reply
Share
Report
pagrus's avatar
Read More

Union-find solution is fun.
One nitpick is time complexity of the UF solution introduces the undefined n in a(n). Yet V is not used, although for (int i = 0; i < n; i++) suggests that it impacts the time complexity.

1
Show 1 reply
Reply
Share
Report
jindalakshunn's avatar
Read More

Can someone please explain ''α(n) is the inverse Ackermann function''

1
Show 1 reply
Reply
Share
Report
yelun's avatar
Read More

Why is this two components? Its just one group isnt it?

4
[[2,3],[1,2],[1,3]]

0
Show 1 reply
Reply
Share
Report
Mo_Kiani's avatar
Read More

Another possible solution is using BFS. We keep a set of non-visited nodes and while it is not empty, we pop a 'seed' out of it to start a BFS, over which we can remove all the connected nodes from the non-visited nodes. We increment count each time we pop a 'seed'. Note I haven't used a variable called 'seed', but it's what "not_seen.pop()" yields.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [list() for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        not_seen = set(i for i in range(n))
        count = 0
        
        while not_seen:
            q = [not_seen.pop()]
            count += 1
            
            while q:
                next_q = list()
                
                while q:
                    for node in graph[q.pop()]:
                        if node in not_seen:
                            not_seen.remove(node)
                            next_q.append(node)
                
                q = next_q
                
        return count

0
Reply
Share
Report
pratikjain227's avatar
Read More

Python solution -

class Solution(object):
    def countComponents(self, n, edges):
        
        parents = list(range(n))

        def find(u):
            if u != parents[u]:
                parents[u] = find(parents[u])
            return parents[u]
        
        for u, v in edges:
            parent_of_u = find(u)
            parent_of_v = find(v)
            parents[parent_of_u] = parent_of_v
        
        map(find, range(n))

        s = set()
        for i in parents:
            s.add(i)
                
        return len(s)

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.